/**
 * https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/589724924/
 * 84. 柱状图中最大的矩形
 * difficulty 2024.12.27
 * 单调栈
 */

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        vector<int> l(n);
        vector<int> r(n);
        stack<int> sk;
        for(int i=0;i<n;++i){
            while(!sk.empty()&&heights[sk.top()]>=heights[i])
                sk.pop();
            l[i]=sk.empty()?-1:sk.top();
            sk.push(i);
        }
        stack<int> s;
        for(int i=n-1;i>=0;--i){
            while(!s.empty()&&heights[s.top()]>=heights[i])
                s.pop();
            r[i]=s.empty()?n:s.top();
            s.push(i);
        }
        int ans=0;
        for(int i=0;i<n;++i){
            ans=max(ans,(r[i]-l[i]-1)*heights[i]);
        }
        for(int i=0;i<n;++i){
            cout<<l[i]<<' '<<r[i]<<endl;
        }
        return ans;
    }
};